//给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。 
//
// 返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。） 
//
// 
//
// 示例 1： 
//
// 输入："banana"
//输出："ana"
// 
//
// 示例 2： 
//
// 输入："abcd"
//输出：""
// 
//
// 
//
// 提示： 
//
// 
// 2 <= S.length <= 10^5 
// S 由小写英文字母组成。 
// 
// Related Topics 字符串 二分查找 后缀数组 滑动窗口 哈希函数 滚动哈希 


import java.util.*;


public class Leetcode1044 {
    Map<Integer, Integer> map = new HashMap<>();

    public static void main(String[] args){
        String str = "gzhvilxpjrgrrezatnuzihvaezrbvalaovljiscsnbmtrnthyijuxuehuiffeaknaywwhlfgfvrlbzbdpgszfpdetyyokkdocmexbvoklmvvbtslafxoepxlonexfinlirflmfjxtedkctiyvsvqknwxbumollkdbquysfvqexksoxrjzwzplmrkfozpumozednrycmrxkasvmiqprunuaaqqdijfxjulluuyxalmhglggemtbgimowlzwmbtgyezcuwsscxrofosjmeohhcwuhblbgbmrqwmifbitwzxkpzetbmjaqytnvnehtajurbkerzsekykgpzeojftklggqzlcgconzxntmfbehpjchsajpgrcnnnmhkudwvoashlcnltxglqrtwxybeyptgvrsvofmilpefzatucmhhbdwopxnyzqrovbkqslftylbiphfgvjddottgpbjkwikniijdxqrkxllnuxxkzpovuazkiebfkzfaosfdaxefkyevetouvpopcmqxdwnnejbsnexbpvlgxpgdmppzrhklmzioedkbdtyuxlyimogtyfsskuvurjdxxnjeptaacvooyfyvseeyuootkiexqnbyatybimqdkbmbedhyufdedhbvkdtdsqygzahnogadgbnmagtumobzsknihjasqfputkgtjrepwsqxpzbdpimjmqltkqajlmkxyfdpohvumbjmtkcoqbtpfbgrnyvtnxfbzxrrdcocbshyxlmqgmpwnpaskosvcpmnobagvbufmwdzbggemrmwqzvadkojmxljcvumpbwbexlkhfzbzijieimpmtyspeikpjjrcbthptzmxufrgbzpkhnwqmxplwwakhrepoknhanzgrtzcjqrcaovbkmvpbgqshfdtugenluyjfwpnackdnazrwuxguynnmgnxsrmgqsheanicnuupjsekkjbubmlzsowrwdmhcvnijixpbpkjxcddjhbucjjmhzbjngflezexzaamyyywabsavwdasergsxopvexfkyolcgjpopxlpmcokwfymfvkkeejlfihhnieplqutfwajcduajkfokgdhglqswawpvaeiofrlqushjlykcmaaezqylzfrmshjldjkwwlnfdjftwqsyczfnrdfywajhepujqpjhvdoktpvokhivjwzbvyifhxxjmtxitnvgebamsuwttixondcxqmabhaskvgpsoxgghkucgbwylxkdcmyyfmlwqdktvqsxeuvnsxlwiskhnmlemnyodjheovpccnndsjdpnsrxbrqmvhrmjqquiblrcmtpkhdenbsufplctuymidzbedsdqbsxpeuqllluxgwgesgevutvnrmxkqajulkyacqnqlxxmezzmnezwzkhxmxvooqirztzsfftbmahxltyoouhsvxaedsgacvyqwgninsmgdzwdirmsrjhpcxmcerivcnykalvvwrlxynmbnzwjyaebvdusydsolzsvwynlmoawydodomzfescurfjkxantfbsvoitdalpnmkysfjybknczgabfwcnpigzzufmrjquppcglavjpqdhbnategojhymfajimkfdsmadriphaiwcyrqzbxosflkvywauptbkowspvhknrdxuolqjnosnalniutvtsebvfqkqcxtrpgjhwdbcxmxqvrilbrfibweettocslcwkduuoszjhqefbkxcynplgdnwotnyqyeejzjesuxiapqssqrdoveodnbmsvuwimwcqamksazakdrzfflchmtyygramodlvnuxrtgmryzefuemfihgzrcnhwynbhjmwbeyaqoeskrkwrlpcdgvwgcuvrbpawmuicbthocynmtjiffxiiemmyczeyvixeernlfgslmmfpcytgcakmhelukknqxypbcbtkiizexvqptixetojnytvhukzyhjdnarwzzujjatczabhhsfiyjaxgypimlgrspixnwxtmghdhaivigwhbfqmmicuoolftlgvtwwxbpsrhqjmzdnkttzsvgjaloqlmdcsmcukmbmlqwqrvhvdrnwxscgbfibjvrcavzayjmjspnajmukdqczrxagwpojxztflhfykkabksoidyrhrclasmvcacgsdvzzrssmiirjjjvarbdyqxoytradmfdgqsknlucbiahxbhfsdcevclnnbiinjjxelaydqogirhfbsdkexygukrjqsmquvvyovsupxpksmuxxyvbdwgdnvswgazgfnjusxfmtotbzyppytrolmvfymvvwezxontpexhftejbxqosltqawtidhguuykdylvswranfklcncjgvnfwwqprhssyovhylcezvqrdtkudvrqqausrkeoihnerrkvpdsdtnbpltsllgqzifbfkpjmcmvztfdzrrdcwesuhtuxhxabmpnxybtknexscqltybkdkjlvaywngtpkqhyfasswozlzzoqtqofzqlrvshmhtfodoipsrkjbbdaztfvuhpgjfnrlajikjyvxvkhyllknsaqkzxrycpooyvhvnphbysuhfrxzyaltuakrzeasxyqdbkdsvlyngshuknxcdrytrhvogsrzmosyzbmnbadnpetagczhhocascojyzuzwukuxvgkfuepiakepykbvxaavayfawropobdtodhmfkmwdokrsoigeuzgxerksxepfncqykwttkotojmdffjoiznlgpiclacyuzjgkaqaijnummpotptguquzaykiszjczmzbstfatflgcraqavriundgkzrxnqyeqjuqdqstloxnnqctagyunytlxzedclzztzwegnighzixvmkfxabnxumvflmtmtdvfzmvtwduggyteagektibddntwdqetpodgzcmugxulcbfmthgqrgxneqctqbtaensknsggueoibzgvdascsstuoidvbscasigbzlkwkmtkwxdstxjweqfnnnihjfazysghlyefhptqaecggexrfuccetxyivqkoapvxwmyjdekotcszhcvfybutluikyqwhjxswrvloqwmpjsamylpbjjdnbaqitpwrwgwjalamcynojjqfguyutglvsyghggehlbzjkdfodfjebfvpskhhxcnegauwgtbmmnsmyerfaycecprwnvwqmuzdvsjjrffhatfhbhrbczmwkgnmzmqkgvipxfdtkriuekdktraebiqrxsphxkqdlbixxyulwhsfivkwqkiwkzihwphhglwuiwblqxctleyaiqphlblyorzutdxujtufktkgkkslnrvkeejzvizivljvvrvqnsydaotfcnzmrttbimakwphdniksoludxiogjpdmazbnohqrxlodjggmmjnsmzprxkgybjqilsgupnyehtkdcapdkcbcpcjgmzukwxmpntutlwljikjxppecreizqeqxuqolhrzsxfldfhyazoakuwrrpxltbsbczjzqjcuyhydxgstlydyasgykimeebpbpnshflijauctortfwjjfxwodmkkrcqkeoofunszmajfppjrvhbprwhrmsglpvsufwmnrolcwxmbvufodtdftlkuazylxwjaqcnvnathtzrxaxpbtpoqyedzwdazmwpygzmikwpbuvnqlejdumkdxzyxublcawwlykjgvhbhdlhpjiztbuvvqolwfaviwbnooekjncyaisibdldxydkdtpulquwmitdnpjgzdpmeprkbregvmgwhjmokhhftozfhhnyyqovuacmnmhclsdyhrnrdtvzfpxcpgnejjyozqkoqzacfabbfzrrokbcxzsfeqkcxkzfjjtqyiurfgtwittlzyvooxywevqqqabjzevlygqimwyrzcfvivndmdgliyovhybyklbcreqbpavyycgvxtsvcilnhrbwpjhbdpmsqyixiyzcywopztvzbabddxofmafxooumrzhfilyegilsupqljcfucgydpglurrwngwaajuopqqiknbykjtcoxkcanzxcsfkcwbmyxiebfkaojfqbyhsnhbqcsolmvoguhaomfvgtvfruajxttmheofzrdvwdifkvmgczbpsijewbfydwhibbavyrgbvruxyjxwyxxrmwnbkhmferwhbhbuurotcyupktkexnbzcskarsqgtmlhsezalnwkddgklhcaytncyfpsgrasgzxvqdyzfufqlkhcfykztcnypmangnuvkcfnfnjunnwdcxbtzvnhgrhqnduozvqbestwyxomfjuurrxvjwfusyqsgilqgihucrwiihmykpgjbwwkzwnagqngtvtufhhpcqpvypybzndnuxnuxcjuvvedglyjbiikrvhrmshsyvyilgitnccwmhenadmkrfvkyutcqrgvhszafvsgpplwndinjxsdvoygofjbuijmtojknwoukqgzqqaxaerzznpelookalbyjcjedekroepjpneruaihgxtunivhmdneljnbhhmlekeefocgfcantsfcystwhkksfoawfgauopzeskqumoavmbeawyylzgabsfsfdldzezvvdidoegzyobmdaeowshuwwxxaswczpaykvkyrwlixxkeonjjnzlrfpbgmrlvgryjqmbdvjhrrkjaqmkgpmtzxhyombreolaobjbixepcwfbzyrhjkvqvdwblxttprawmlrtikvukydhtobvatgvieoxqrbtagkbjwiuzyunjdquxmzcejeoowlupstmkqzfrguffffpizqlnighdpsaabcqtrxguhyhhzrrsdwlpgwyygbpudpxdxqgckmpvzjsnmhznhzkkceomwlrdnjjarasomfraiydswbzwvlygygbtfoawwsflhtgexbaeotfhfokiaxeerqecdwbkuoutdahpbvosbxjlpvgaubsfpgmppqmsffgfwcphthaawskscuwhbjvqthhxyfcvzkfismdeoguryafwdfstrndoqwjytbganmbpinjcnemijucqhekatenftxwycbylehctyxmwohhaqlilecxlwhjixzgstnpvqjqiedkvgcthaafzurjkxskymkateofvmewwalcmywtrlnhtpxoknmjrmajhiouxvytttuwbarlewegptlourwhpzejayoyzjygcnjhqmsgneuajfyyweditelealzjnwwdqnznmbheppnqttoechqmnrqgnhojehnwauotgkxqwswcyfmfefuycbzqutzpcxzeziwsewnihvidkyxupyjxowtpabjgincjaaxahbadxizimilhgqwbfasephsoncpyokqcxhwnqqmftgnzrpotemweubivjtlkefhefgiingkukpoqakkizzbyryqlthpwyiiwxtszdrucddvwkbvazbwwfyrsusdqzqlbbghmgogfkabaopenezmykvdabjnovrebhpanpguamvbswuebryanmaifxwwvxsqskmoqmbvrkwjgkkictbrwswnvbapgbiuxbnbwymyposzlwgklbckzzxwtxgpsxjlkfympahxftmarlqrleoinppthrdxiqasapmediekmxpwwgawbtlmgomejcxkpepeefojswvdlyoafwiwxdldnrhirgnevkgpzksxwzppmdvlwnsynwzhiizzgagjxbfmnyaxfdkwxxanxbmmbauvhbjetqkcexmyrlgyxnmjodmuwjrxaiyzwkdaaerexgqkvwbfvaoakofuikxiiilodglyzjxuhespifzeozjxwzurbyjclqiyjyowwokemiakbnjlpvgzaqqklnhbdaxldifunjtqcvubnpeetnhrdnpemjwzxuqwbfdkbjbkzbrdqjmdtqbnxsbqjmbmzctyrsbjobzfevvytuhsgwxgilffdasxhzhihfpiymqzptvssmvpayupggepznusyboilojxnotagbmewjfmjbdduwjrdnuooxkhtozramtlxaunvzczcjogzmchrivzpiieshwfeassayddsfhleqjdnloinszgbdjngjhecmgodpmowwlpvmcgsuuerzhezeyejhpnlvesiiudniyzyphmwnkhvreciyskiyletzqvjopzbfbtquixhbyoqywhncageqbiugvvnndhfoayehaofbucmonrpvvqjjmnbcgezwfvqwnyisjcikslnywworgqkumbigekrfmihsmltvmuewlocqjyyoxdslamhjermikteawoxfquuzwozoxfvhfqozzfxupxmrzirstscqefztavjluurbaziiuixttyuadbvophauiwzxodqsllkhuqofdvwpfsphziddlvlkztipauevrcrksvpuwgxltithvkswoftkxygucnbwalovfjdlsidhqiixjluxgbdzvoaaulsyvhifcedghyzbtjqjfduyqdkinmpmyovqwdexnrpzbnazyfqvjqwmcrqufmawupnxefaixunlfwzzjpyoqqugykmqojgdiwemaujcqsdyvlaglksihcsywwbbgzhpejlmvbwtxlbakvgybodjhrtfxmrwybdojqgkvzacztstuywoklmxfmdewbkasogtabtsbaytwysxeupuiuwxoogsxqasbgtybqxjosohqzfvtosxkobcosyyhipnzwmlxbgqvhgjernpyrcvuayttskiqrrwwwfzlbsjyetqmspttlpitbacrtxojzeldtudpbigrbjbjgkwukllqdupesnmuendgdylcvrrwyjfizkpilhgisbhiolojsqbmqehswaptqvdznlesveppplsnzpuegefcwhhrqnolbgkrmejhynvsbasxmpopkxpepjfiqsgpbqnyfhrfzcfyitpkmzsfmkhleligfqzjusccpbtegjewrpgkjqdyfawjabqpjsfjoytjqhqkunrvzpzxjbagggnzftvrgjyixzkkddjroukpvovlajnzlytcdmzpyxpvxkfeqolndinwonmjwacfazpvrzgtpzqcfewzsrxzoxwxsfyvwjflhnxxiqsapudhvwthxfsjrabbltmurwnfwsxnfvvdzwekotfkwabeameutbfwsgvvmqaqexgxqeavivnysdrkeyiwuyoviparneaudpyqebjmqtadavcuhzwmaoewnwhznouqpymeyozldgepyjlhnrszxwsurzgqrtyilwzjvypcrqayswtqachqbkptzlnjurnawzqyaqpamaljmtejfpyrrvmducyrdjjbbtxtbqrxssqijpctzcvxcclsrwxwpdvnolysqgnllieezdwtvvzujanextmfbykqogkcwcubcxdqyyieifzemcdqswngmopoufbrnovtccedaldabxmqaabzqltcjrttxizevnrnmtmyivzqcuqgpdutiiyqhfxxwemmyiixlomiuhqzktklxwgnuomxsvwdflhkrrmwwvzfwmnerkqgakatfyrceuzywyxfdhisixzhavjlmehyklvhjztxepogfyvyqpogwqxrfqomcfgmysohaptzipfmjtnsqfktexqqzryglcbzsirwcjcfynmlbfziadzibaisdosapioaqgzmcnhjjoyungnvzmkvpzeumfbulbtvfdnzbfscumizqcapmeaouhoprcofqjpdsnlqmkphegtltsknunzigmixnagfgmhwrghwvwegaijwnkmraffvgttlmcklszyuyohkavhgnwkjvfpbxbasxmgrgcbyxilhondfmxrpnwuijujufponedqdnfficgwttnxemcbjlrgsbmslwjjqoslwneuqymldajdzdyiztddptxaaitmpmizwiodajusscojvgryvpfwuvsvsnotfnvwqzwroamjnaqmyacodoedsjbjdtdregvzxyovybajyxccjzafjeyiqsaxiflusiyhthbkrvzpamckjglwtlzusbfvtbxxcxdxpwwavcgmipwfecupzhphgsjabgkzwsbabdcqtphwqkxpsfwwuklsfdiiznpdcohcclmnamcovugpzbrehxfotjbdxxvpyfkcnpnwvbwkqeldcbkjrxyvvkqoxraqwaftgutgfshsdsywvsicbrwyjhfbzkhxvusewmkqjrtdlnvmtmkwxorfbreskduvclpqhhisjfuviilgdxwldnxwxdfmibczmyptjhawgpzquvpiemjlbpnpocwquecqkxxzwaxgmvwcmjmdacnauohqtajknuprxzuwbgzrvisbjjadnyxawzxyfqtmndhhfuwnlpsyeqwuzghpcmbicixfbmwrfrcugdplnekjzmjxnashqhskyeaoudaqjhgkwortfhzqarkqdbitmqqgwdukdgjzejtodegpredlwkeyygcftzawdrsowrzjlscbxxqkiryxyruvswmxngfkctjglfdxrqieoiajoiakmyqxoguwuffsbtngguekneeglbvhiqpiflyqkroxhdfikwhmotchizajztfihrzmmvnwqdjvspsmbetswubaafvhvhkkusmyskktcsnycodmjmvdtgpprnvhknbollwhrqueqlavuljmkphapixzkhoflhohwmdmhaubtwholnzpefgkgzzhkzdnntrufoyzwepfxmtfnpbewyoiacedmwedgyjdkxywxwbokcfpxywrkvbcqwwiqfyiygqqaoxtssszyjnbywofkwknlkmsmylofgjemslpwmcbrsjuxxehwfevkijufgbjszicufklgvcaxvzvzkxqxtowgrgofbwkwfygefwxcyxlgjgdcmxpvihgvwxoqwpmjkrewauygrnfgoeqrgpwvtbkpmbsxexqoecfeatubblgnmrtzzvsibviojfjftxiqxhxmjisxlgslhudjbrbrjrsdwrdxwmdltiymdmmgcklpmgfjntehaefmvukfpfsbbjsdtcpcppxkwoqgempyyobqaqdkohepjcasbfornxehvzfnochfmmjegwdesoyexqqzirutddokoofrhqwqfeovjikuhskzciwmbdfurdxkakccejvnizgmxaxffvxvzfanuzaiaayeqrcqfahqowhzrhxnivygwbozthyvofuutqnjukgmsxftjflcyqptiryxuzhrwnqfxqblunmikfylhpwofmfjeinpbkeojxypfdbrracaiuiwbwamkvozgguczzwxmbvozziwygpccemzqtgzzeqwblnitbrinqrbjholgwcivaevkzavnvkuxqemffjbwcsxeivpqqrfwrfshelxmyujyvguymqoavskmpegacbqhhpljsaapaeuiljkgbtlnlebubtinfynlhgvadmxhbzbjifsbtbitzinrgajbrhpecponumabqgecekdxydqufzfzbzoutrbypenuufgmajvndygalnnrggftlnuthaecczemghagdopomednlzgpryclyruelvpmvndgzaavopkixsgkrnlmnvstekraeretfdstjzcnwvfrhzmwmaizndibcuxnpxivsipyjnwxirxtodlzdknaughjltgpcszuxitcmamhzgklcclxrwichaiwpsrcntsdqfqwxdypvxpzjhfkktvtvwsqokoztkrdebtbbsbsrmaaigscicsdjktakejgdigqljuxaqhwazkgiqtwlcalpuhjpavpvwohkxnjknlwngkgetadoquzgjkllekmmbzkm";

        Leetcode1044 leetcode = new Leetcode1044();
        String ret = leetcode.longestDupSubstring(str);
        System.out.println();
        System.out.println();
        System.out.println(ret);
    }

    public String longestDupSubstring(String s) {
        System.out.println(s);
        if (s.length() <= 1) return "";
        if (s.length() == 2) {
            if (s.charAt(0) == s.charAt(1)) return s.substring(0, 1);
            return "";
        }

        int poc = 0;
        int l = 1, r = s.length() - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            System.out.println("l="+l +";r="+r);
            if (search(s, m)) {
                poc = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        Integer idx = map.get(poc);
        if (idx == null) return "";
        return s.substring(idx, idx + poc);
    }

    public boolean search(String s, int l) {
        System.out.println("search len : "+ l );
        HashSet<Long> set = new HashSet<>();
        
        long b = 31;
        long a = 1;
        long m = 1<<63 -1;
        long h = 0;

        for(int i=0; i< l; i++){
            h = (h * b + (s.charAt(i) - 'a')) % m;
            a = a*b%m;
        }
        set.add(h);
        // System.out.println(s.substring(0,l));

        for (int i = l; i < s.length(); i++) {
            h = (h * b + (s.charAt(i) - 'a') - (s.charAt(i - l) - 'a') * a) % m;

            // System.out.println(s.substring(i-l+1,i+1));
            if (!set.add(h)) {
                map.put(l, i - l + 1);
                System.out.println("search len is match: "+l);
                return true;
            }
        }
        return false;
    }
}